import tool.TreeNode;

import java.util.HashMap;

/**
 * @Description: 从中序与后序遍历序列构造二叉树
 * @Date:Create in 10:26  2022/8/1
 */

/**
 * 来看一下一共分几步：
 * 第一步：如果数组大小为零的话，说明是空节点了。
 * 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
 * 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
 * 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
 * 第五步：切割后序数组，切成后序左数组和后序右数组
 * 第六步：递归处理左区间和右区间
 * */
public class buildTree0106 {
    HashMap<Integer, Integer> map;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return findNode(inorder, 0, inorder.length, postorder, 0, postorder.length);

    }

    public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
        if (inBegin >= inEnd || postBegin >= postEnd) {
            return null;
        }
        int rootIndex = map.get(postorder[postEnd - 1]);
        TreeNode root = new TreeNode(inorder[rootIndex]);
        int lenOfLeft = rootIndex - inBegin;
        root.left = findNode(inorder, inBegin, rootIndex, postorder, postBegin, postBegin + lenOfLeft);
        root.right = findNode(inorder, rootIndex + 1, inEnd, postorder, postBegin + lenOfLeft, postEnd - 1);
        return root;
    }

}
